package 简单.位运算;

/**
 * 对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。
 * <p>
 * 例如，整数 5 的二进制表示是 "101" ，取反后得到 "010" ，再转回十进制表示得到补数 2 。
 * 给你一个整数 num ，输出它的补数。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/number-complement
 */
public class 数字的补数_476 {

    public static void main(String[] args) {

        System.out.println((long) Math.pow(2, 31));
        System.out.println((long) 0x7fffffff);
        System.out.println(Integer.MAX_VALUE);
        System.out.println(Integer.MIN_VALUE);
    }

    /**
     * 第一步：
     * 找出num转二进制之后的第一个1
     * 转换思路：
     * 求2的n次方<=num，n的最大值，因为1 <= num < 2的31次方，所以n的范围[1,30]
     * 方法：遍历，二分查找
     * 第二步：
     * 求[0,n]位全部为1的二进制数字
     * 假如 n=3是最高位
     * 那么1 ? ? ?，其实有4个位置
     *
     * @param num
     * @return
     */
    public static int findComplement(int num) {
        int highbit = 0;
        int temp;
        //从30次方开始遍历，碰到2的n次方<=num时停止循环
        for (int i = 30; i >= 1; i--) {
            if (1 << i <= num) {
                highbit = i;
                break;
            }
        }
        //num   ... 0 1 1 1 1 0  n=4
        //temp  ... 0 1 1 1 1 1
        //n^t   ... 0 0 0 0 0 1  -->得到num二进制的补数
        //2的31次方超过了int的最大值=2147483648
        temp = highbit == 30 ? Integer.MAX_VALUE : (1 << (highbit + 1)) - 1;
        return num ^ temp;
    }

    /**
     * 二分查找
     *
     * @param num
     * @return
     */
    public static int efficientFindComplement(int num) {
        int highbit = 0;
        int temp;

        int left = 0, right = 30;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if ((1 << mid) <= num) {
                highbit = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        temp = highbit == 30 ? Integer.MAX_VALUE : (1 << (highbit + 1)) - 1;
        return num ^ temp;
    }


}
